The well-known Fourier transform has and remains of fundamental importance in mathematical analysis and is the subject of volumes of study. It has been used for many years as an efficient computational tool for accomplishing certain common manipulations of data. For example, the Fourier transform may be used to approximate events or phenomena occurring in a two-dimensional plane as might be the case when performing signal processing translations of digital information into graphic or other visually perceivable intelligence. Practical applications for use of the Fourier transform are enormous in the digital signal processing arena. Further, other transform equations such as the Radon transform used in tomography are commonly converted to Fourier transform equations to facilitate their calculation.
Due to its linear nature, practical applicability of the basic Fourier transform has been limited due to the length of time required to derive meaningful calculation results for multidimensional Fourier transform equations. Until the mid 1960s, for a medium-sized Fourier transform having, for example a thousand points (n), a two-dimensional calculation using simple linear matrix multiplication calculation methods would require (n.sup.2) or 10.sup.6 multiplications.
What is now known as the fast Fourier transform (FFT) algorithm became generally known in 1965 primarily through the efforts of J. W. Cooley and J. W. Tukey who published their findings in "An Algorithm for the Machine Calculation of Complex Fourier Series" Maths. Comp., 1990:297-301, April 1965. This paper is herein incorporated by reference to the extent that the teachings thereof are valuable to an understanding of this invention. The emergence of what has come to be known as the Cooley/Tukey or simply C-T FFT algorithm was a milestone in the history of computing. The FFT algorithm generally changed computation of the discrete Fourier transform from a linear (n.sup.2) process to a logarithmic (n log n) calculation. The difference in calculation time was immense. For example, the 10.sup.6 calculations required by the Fourier transform example above reduces down to only approximately three thousand calculations using the FFT algorithm. Such reduction in the required number of calculations and the resultant increase in calculation speed has had a tremendous impact on the practicality of use and expanded uses for the FFT in digital signal processing applications. For example, signal processing using CD ROM's has become commonplace as a result of processing of the digital signals with FFT algorithms.
Since their inception, the C-T type FFT algorithms have predominated the art of Fourier transform calculations. Over the years, numerous variations of the C-T FFT algorithm have been posed, as for example, those discussed in the paper entitled "What Is The Fast Fourier Transform?" by W. T. Cochran; J. W. Cooley; D. L. Favin; H. D. Helms; R. A. Kaenal; W. W. Lang; G. G. C. Mailing, Jr.; D. E. Nelson; C. M. Rader; and P. D. Welch, (IEEE Trans. Audio Electroacoust., 15(2):45-55, June 1967), which is herein incorporated by reference.
The standard approaches or techniques for processing the C-T FFT-type algorithms have not changed much over the years. Typically, calculations involving one-dimensional FFTs are manageable, since the calculations can be rapidly continuously processed to a result. As the number of FFT dimensions increases, however, so does the time and difficulty in performing the calculations. For example, the typical method used to process the calculations of a two-dimensional FFT which can be presented in a matrix form, is to perform all of the calculations for each row of the matrix and to perform all of the calculations for each column of the matrix, and then perform the cross product (i.e., row and column) calculations by using parallel processing techniques. This approach is generally referred to as the "row-column" or "butterfly" approach. From an overall time perspective, the calculation time required for performing the individual row and column calculations is relatively small compared to the time required to perform the translation calculations between the parameters of rows versus columns. For multidimensional Fourier transforms, the processing is typically performed with parallel processors. As the size of the FFT matrix increases, the processing time involved dramatically increases and often is only attainable by the use of super computers.
As technology has advanced so have the applications for the Fourier transform and the need for rapidly calculating huge multidimensional Fourier transforms. If huge Fourier transforms, such as 10.sup.6 .times.10.sup.6 point Fourier transforms could be rapidly calculated, many problems and practical applications for use of the Fourier transform in applied signal processing could be implemented that are not practical today. For example, in tomography, such processing speed reduction might enable pictures of a pumping heart to be obtained. Similar needs for reducing the time to obtain useful results from the processing of radar signals exist. It would be desirable to have a technique that would permit at least a one and possible two orders of magnitude decrease in the speed of processing complex (multidimensional) FFTs. It is also desirable that such technique be adaptable for implementation with existing semiconductor and computer technology. It is believed that the present invention will provide the key to achieving such techniques. Historically, there has not been much done to change the way FFT algorithms are perceived or written. This was due in large part to the success achieved by the butterfly techniques as a teaching and programming device. Other approaches to processing the C-T FFT algorithms, however, have been introduced. One of such approaches, which is important to this invention is the "tensor" product formulation of the FFT, which was first introduced in 1968 by M. C. Pease in an article entitled "An Adaptation of the Fast Fourier Transform for Parallel Processing" (J. Assoc. Compt. Mach 15(2):252-264 April 1968). The tensor product approach did not receive much attention until it was successfully programmed on vector computers such as the Cray X-MP and Cyber 205 computers by Temperton in the early 1980s. This invention incorporates the tensor product formulation principles in characterizing the FFT algorithms in a unique manner which enables the C-T FFT algorithm to be written in a "dimensionless" format that can be readily implemented in reconfigurable hardware for evaluating one-, two- or three-dimensional C-T FFTs in a manner that significantly reduces the processing time.